A host computer system used by multiple entities (people or other devices) usually maintains accounts for the entities. To access data owned by, and services provided to, an account, an entity must first prove his/her/its identity. The entity, also called the “user,” may be a person, a physical device, or a collection of software. A process by which the user proves his/her/its identity is called “authentication.”
One of the most common methods of authentication is password authentication: verifying that the user has provided a correct password. When the user sets up his/her/its account, he/she/it specifies a new password—usually a string of characters that may include letters, digits, symbols and control characters. The host computer system stores information about the password sufficient to verify whether or not a trial password, provided by the user at a later time, is correct (is identical to the password). The information stored about the password that is used to verify whether or not the trial password is correct is called a “password verification data set.”
In the early days of computing, the password verification data set was the password itself. To authenticate the user, the computer system obtained the trial password from the user and compared it to the password stored in the password verification data set. This password authentication method is simple but has a major flaw: a person who can view the password stored in the password verification data set can use the password to impersonate the user.
An early improvement to the password verification data set was storing an encrypted version of the user's password instead of the password itself. When creating the user's account, the host computer system applied a “one-way function” to the new password, and an output of the one-way function was stored. The one-way function modifies its input in a way that is very difficult to reverse; from an output of the one-way function, it is hard to determine what its input was. The output of the one-way function is called a “hash.” Looking at the hash derived from the user's password, it is not easy to determine what user's the password is.
As host computer systems were entrusted with more important data and services, the rewards for determining the password of another user grew. A method for determining another user's password from a password verification data set became known as “cracking” or an “attack.” Today, a password attack generally starts when an attacker gains access to (steals) a password verification data set of a targeted user. The attacker then programs his/her own computers to perform a same password authentication method that the host computer system uses, and the attacker attempts to authenticate many trial passwords until the correct password is found. Three common password attacks are dictionary attacks, brute force attacks and rainbow table attacks. A dictionary attack tries to authenticate all passwords in a list of likely passwords. A brute force attack tries to authenticate all possible passwords less than a certain length (possibly with other restrictions). A rainbow table attack uses a large, pre-computed table of passwords and hashes to speed up the process of finding the correct password.
A cryptographic key can be used, in conjunction with an encryption method, to encrypt and decrypt a data set. If the cryptographic key is generated from a password, the cryptographic key may be vulnerable to some of the attacks described above.
To make password attacks more difficult, computer scientists invented the concept of “salt.” A salt is a string of characters or bits that varies from user to user and is mixed with the user's new password and trial password before applying the one-way function. The password verification data set was expanded to include both the hash and the salt. The salt is usually randomly generated when the user's account is created or when the user changes his/her/its password.
Other techniques for resisting password attacks have been suggested but are not widely used. For example, “password strengthening” adds random bits to the user's password before applying the one-way function to create the hash that is stored in the password verification data set. The random bits are not stored in the password verification data set or in any data storage device. If 20 random bits are added, then an attacker has to perform one million (two raised to the power of 20) times as many computations, on average, to determine the correct password. A disadvantage of password strengthening is that authenticating a legitimate user's password also takes longer. Another technique, “password stretching,” makes the one-way function more time-consuming to compute, for example by applying the one-way function repeatedly in a loop. Password stretching also slows down both password attacks and the authentication of a legitimate user's password.
An important weakness of most password authentication methods is that they store password verification data sets of many users in one place, typically in a single file or database. Numerous times, hackers have broken into host computer systems and stolen the data in these files or databases. The password verification data sets stored in a central location may be considered vulnerable.
Another proposed technique for resisting password attacks is distributing the password verification data set among a set of cooperating computers. To successfully attack a host computer system that uses this technique, the attacker must gain access to multiple cooperating computers, a more difficult task than gaining access to a single host computer. Implementation of the proposed technique is complex and may not protect the host computer system against an attacker who gains root access to one or more of the cooperating servers.
Other authentication methods may achieve greater security by obtaining other types of information from the user besides, or in addition to, the password. For example, bio-metric authentication verifies the user's identity from a unique attribute of the user such as a fingerprint. Authentication can also be based on verifying that the user has an object, such as a smart card or a security token. Multi-factor authentication obtains several types of information from the user, such as a password and data from a smart card, or a password and a fingerprint. Multi-factor authentication may offer greater security than password authentication but has several disadvantages: 1) the additional factor(s) usually require additional hardware, such as a fingerprint reader or a smart card, that has a cost, 2) presenting the additional information may inconvenience the user every time he/she/it logs in, and 3) if the user loses the smart card, or if the fingerprint reader breaks, then the user cannot log in at all.
The other techniques for resisting password attacks may be used in conjunction with password verification data sets and password authentication methods described in this disclosure. The password verification data sets and password authentication methods described herein may also be used with multi-factor authentication as long as one of the authentication factors is a password.
A different approach to authentication is to challenge the user with security questions in addition to the password. Before or after the user enters his/her/its password, the host computer system may ask the user one or more security questions that only the user (hopefully) can answer correctly. Incorrect answers to one or more security questions may cause authentication to fail. In some implementations, the security questions are asked only if the user does not have an expected data element, such as a cookie written on the user's hard drive during a previous session. Requesting answers to security questions may also be used as an alternative to password authentication if the user claims to have forgotten his/her/its password.
Multi-factor authentication and requesting answers to security questions may be used in addition to password authentication, but are not password authentication methods as defined herein.